Range Mode Query
Operations
$ n以下の正整数の列$ (a_1, a_2, \dots, a_n)を扱う
空間計算量$ \Theta(n)
$ \mathtt{new}(a_1, a_2, \dots, a_n)
与えられた列に対応する構造を作成する
時間計算量$ \Theta(n \sqrt{n})
$ \mathtt{mode}(l, r)
$ a_l, a_{l+1}, \dots, a_rの最頻値を取得する
時間計算量$ \Theta(\sqrt{n})
Summary
列を平方分割し、以下の情報を管理する
各ブロック間の最頻値と頻度
各要素について、その値が手前にいくつ存在するか
各値について、その値の index を昇順に並べた配列
端数に含まれる値について、現在の頻度を超える部分から線形探索を行う
https://gyazo.com/202d0fe6af4c7334686718aa18e88e80
References
Notes
最頻値の他にその頻度も取得することができる
空間を気にしないならば、ブロック毎に prefix の各値の個数を保持すると単純になる
Implementations
Problems